class Solution {
public:
    int dp[100005][2];
    int maximumSum(vector<int>& arr) {
        dp[0][1] = -1000000000;
        dp[0][0] = arr[0];
        int ans = max(dp[0][0], dp[0][1]);
        for (int i = 1; i < arr.size(); i++)
        {
            dp[i][0] = max(0, dp[i - 1][0]) + arr[i];
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + arr[i]);
            ans = max(ans, max(dp[i][1], dp[i][0]));
        }
        return ans;
    }
};